/**
 * 用于生成FDT
 * 创建对象之后用addEdge建图
 * 之后执行init和getFDT即可获得FDT
 * 复杂度nlog
*/
import {FDT} from './fdt';

export class Edge {
    u:number;
    v:number;
    next:number;
    isTE:boolean;
    constructor(){
        this.u=0;
        this.v=0;;
        this.next=0;
        this.isTE=false;
    }
};
export class Graph {
    N:number;//图的节点数
    num_e:number;//边计数变量
    dfnT:number=0;
    edge:Edge[];
    st:number;//源点
    ed:number;//汇点
// 点的属性
    first:number[];
    fa:number[];
    dfn:number[];
    rak:number[];    
    sdom:number[];
    idom:number[];
    pre:Array<number>[];
    bkt:Array<number>[];
    
// 冰茶机
    dsuf:number[];
    val:number[];

    fdt:FDT;

    constructor(N:number,st:number,ed:number){
        this.fdt=new FDT(N,st);
        
        this.N=N;
        this.num_e=0;
        this.st = st;
        this.ed = ed;
        this.edge=new Array<Edge>(N*10);
        this.first=new Array<number>(N+10).fill(0);
        this.fa=new Array<number>(N+10).fill(0);
        this.dfn=new Array<number>(N+10).fill(0);
        this.sdom=new Array<number>(N+10).fill(0);
        this.idom=new Array<number>(N+10).fill(0);
        this.rak=new Array<number>(N+10).fill(0);
        this.pre=new Array<Array<number>>(N+10);
        this.bkt=new Array<Array<number>>(N+10);
        this.dsuf=new Array<number>(N+10);
        this.val=new Array<number>(N+10);
        for(let i=0; i<=N+9; i++){
            this.pre[i]=new Array<number>;
            this.bkt[i]=new Array<number>;
            this.fa[i]=i;
            this.dsuf[i]=i;
            this.val[i]=i;
        }
    }
    public addEdge(u:number,v:number){
        this.pre[v].push(u);
        this.num_e++;
        this.edge[this.num_e]=new Edge();
        this.edge[this.num_e].u=u;
        this.edge[this.num_e].v=v;
        this.edge[this.num_e].next=this.first[u];
        this.first[u]=this.num_e;
    }
    private dfs(x:number){
        this.dfn[x]=++this.dfnT;
        this.rak[this.dfn[x]]=x;
        this.sdom[x]=this.dfn[x];
        for(let i:number=this.first[x];i!=0;i=this.edge[i].next)
        {
            let v=this.edge[i].v;
            if(this.dfn[v]==0)
            {
                this.edge[i].isTE=true;
                this.fa[v]=x;
                this.dfs(v);
            }
        }
    }
    private min(x:number,y:number):number{
        if(x<y)return x;
        return y;
    }
    private get(x:number):number{
        if(this.dsuf[x]==x)return x;
        let r:number = this.get(this.dsuf[x]);
        if(this.sdom[this.val[this.dsuf[x]]]<this.sdom[this.val[x]])
            this.val[x]=this.val[this.dsuf[x]];
        return this.dsuf[x]=r;
    }
    private getIdom(){
        for(let i=this.N;i>1;i--){
            let p = this.rak[i];
            // console.log(p);
            this.pre[p].forEach((j)=>{
                this.get(j);
                this.sdom[p]=this.min(this.sdom[p],this.sdom[this.val[j]]);
            })
            this.dsuf[p] = this.fa[p];
            
            this.bkt[this.rak[this.sdom[p]]].push(p);
            this.bkt[this.fa[p]].forEach((j)=>{
                this.get(j);
                // console.log(j,this.rak[this.sdom[j]]);
                if(this.sdom[this.val[j]]==this.sdom[j])this.idom[j]=this.rak[this.sdom[j]];
                else this.idom[j]=this.val[j];
            })
            while(this.bkt[this.fa[p]].length)this.bkt[this.fa[p]].pop();
        }
        for(let i=2;i<=this.N;i++)
        {
            let p = this.rak[i];
            // console.log(p,this.idom[p] , this.idom[this.idom[p]])
            if(this.idom[p]!=this.rak[this.sdom[p]])
                this.idom[p] = this.idom[this.idom[p]];
        }
    }
    private genFDT(){
        // console.log(this.idom)
        for(let i=0;i<this.N;i++){
            if(this.idom[i]!=0)
                this.fdt.addEdge(this.idom[i],i);
        }
        // console.log(this.fdt)
        this.fdt.init();
    }
    public init(){
        this.dfs(this.st);
        this.getIdom();
        this.genFDT();
    }
    public getFDT():FDT{
        return this.fdt;
    }
};

